package org.lanqiao.practice_2;

import org.junit.Test;

public class TestDriver7 {
	// 归并排序
	public static void merge(int[] ar, int start1, int end1, int start2, int end2) {
		// 处理当两个有序的一段数组融合的时候
		int[] temp = new int[end2 - start1 + 1];
		// i,j分别是两段的游标
		int i = start1, j = start2, k = 0;
		// 分别对两段的数据进行大小排序
		while (i <= end1 & j <= end2) {
			if (ar[i] < ar[j]) {
				temp[k++] = ar[i++];
			} else {
				temp[k++] = ar[j++];
			}
		}
		while (i <= end1) {
			temp[k++] = ar[i++];
		}
		while (j <= end2) {
			temp[k++] = ar[j++];
		}
		k = start1;
		// 把排序好的数组赋值给原先的数组
		for (int tem : temp) {
			ar[k++] = tem;
		}
	}

	public static void mergeSort(int[] ar, int start, int end) {
		if (start < end) {
			// 对数组进行切割排序
			int index = (start + end) / 2;

			mergeSort(ar, 0, index);

			mergeSort(ar, index + 1, end);

			merge(ar, 0, index, index + 1, end);
		}
	}

	@Test
	public void test() {
		int[] ar = { 5, 2, 10, 8, 23 };
		mergeSort(ar, 0, ar.length - 1);
		for (int i : ar) {
			System.out.print(i + "  ");
		}
	}
}
